\chapter{Introducción}
	\label{chap:introduccion}

	\epigraph{La inteligencia consiste no sólo en el conocimiento, sino también en la destreza de aplicar los conocimientos en la práctica.}{Aristóteles}

	\section{Introducción}
		%\parindent 1em 
		La Inteligencia Artificial (IA) es la ciencia que estudia cómo hacer programas \textit{``inteligentes''}, capaces de tomar decisiones racionales. De ahí que sea una de las áreas de investigación más activa que hay en computación y sobre la cual se realizan múltiples publicaciones.\\
		
		Dentro de esta área, se encuentra la tarea del \textit{reconocimiento de patrones}, en la que patrones sencillos pueden ser descifrados por computadoras, pero se busca que cada vez las máquinas sean capaces de encontrar patrones más complejos.\\
		
		La presente tesis busca brindar un mecanismo para reconocer un patrón complejo. Se van a tomar los juegos de estrategia como punto de referencia y como ejemplo de patrón complejo. En particular, se va a utilizar el ajedrez dado que tiene muchas características que resultan pertinentes para satisfacer la hipótesis que se desarrollará a lo largo de esta tesis.

		\subsection{Ubicación del presente trabajo en el área de la IA}
		La IA se ha caracterizado por diseñar algoritmos que emulan ciertos comportamientos humanos. Principalmente en tres áreas importantes: toma de decisiones, razonamiento y aprendizaje. Este último es el punto sobre el que gira esta tesis. 
		
		El aprendizaje, desde el punto de vista de propósito, se puede clasificar en: \textit{sintético} (que consiste en crear conocimiento nuevo) y \textit{analítico} (que consiste en organizar conocimiento para cumplir algún objetivo).\\

			Este trabajo se centrará en el desarrollo de una nueva red neuronal de retropropagación. Esto es un proceso de aprendizaje sintético, debido a que el aprendizaje está basado en una serie de ejemplos con su respectiva valoración realizada previamente y la red debe ``\textit{aprender}'' a obtener las mismas conclusiones.

		\subsection{Inteligencia Artificial y Teoría de Juegos}
			La Teoría de Juegos, desde sus inicios en 1944 \cite{Neuman_1944:uq} cuando von Neuman y Morgenstern la propusieron con aplicaciones principalmente en el área de la investigación de operaciones, ha evolucionado de manera vertiginosa y un área donde se ha investigado a profundidad es la IA. Esto se debe a que los juegos ofrecen un área de estudio que involucra: toma de decisiones y aprendizaje. Resulta muy importante para la IA contar con mecanismos que apoyen dichos ejes; es en este punto donde reconocer patrones complejos toma importancia como una alternativa a las estrategias tradicionales aplicadas hasta ahora en juegos.

			\subsection{Clasificación de juegos}
				Para su estudio y programación, en IA los juegos son clasificados según varios autores, entre ellos Robert Gibbons en su libro ``Un primer curso de teoría de juegos'' \cite{Gibbons_1992}, basado en el nivel de conocimiento que tiene cada adversario de las opciones que tiene su rival y del número de rondas o estados a los que cada jugador tiene que enfrentarse en el desarrollo del juego. La clasificación es la siguiente:
				
				\begin{table}[h!]
					\centering
					\begin{tabular}{|c|c|c|}
						\hline
						& \textbf{Estáticos} & \textbf{Dinámicos}\\
						\hline
						\textbf{Información completa} & Piedra papel tijera & Ajedrez\\
						\hline
						\textbf{Información incompleta} & Dilema del prisionero & Póquer\\
						\hline
					\end{tabular}
					\caption{Clasificación de los juegos}
					\label{tab:clasifJuegos}
				\end{table}
		
				\begin{enumerate}
					\item \textbf{Juegos estáticos con información completa:}
					En este caso ningún jugador observa las acciones de ningún otro antes de tomar sus decisiones, y cada jugador solo tiene un turno. Luego de que un jugador ha realizado sus acciones, este recibe sus respectivas ganancias, que son el resultado de la combinación de las acciones de todos. Un ejemplo de este juego es ``piedra, papel, tijera'' en el que cada jugador sabe lo que el adversario puede sacar, y él tiene las mismas opciones para elegir. El ganador se obtiene al evaluar las decisiones de cada jugador.\\
					
					\item \textbf{Juegos dinámicos con información completa:}
					Son los juegos en los que los jugadores reaccionan de manera secuencial y cada uno conoce por completo la decisión que hicieron los otros. Es importante mencionar que se conoce perfectamente el objetivo del rival. El ajedrez es un claro ejemplo de este tipo de juegos. Este ha sido muy estudiado en Investigación de Operaciones e IA desde la Teoría de Juegos.\\
					
					\item \textbf{Juegos estáticos con información incompleta:}
					Todos conocen el juego, sin embargo no conocen todas las opciones que los rivales tienen para hacer. En el mejor de los casos se cuenta con una probabilidad y se cuenta con el objetivo que tiene el rival, pero no se conocen sus acciones. Por lo general ocurren de manera simultánea y las ganancias ocurren luego de cada ronda. Un ejemplo de este tipo de juego es el dilema del prisionero, en el que la ganancia se obtiene sólo si ambos jugadores logran ponerse de acuerdo en la decisión, sin querer perjudicarse mutuamente.\\
					
					%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
					%% Revisar sangría de toda la sección!!
					\item \textbf{Juegos dinámicos con información incompleta:}
					En estos juegos uno de los jugadores no conoce qué acción ha tomado el otro jugador en su totalidad, pero las acciones ocurren de manera secuencial. El ejemplo clásico de este tipo de juego es el póquer, porque cada jugador hace una serie de apuestas basado en probabilidades y debe poner presión a los adversarios realizando apuestas de manera consecutiva y manteniendo el orden. Además, es importante tener en cuenta que los estados en el póquer se basan en el número de fichas con que se cuentan en cada fase de la partida.\\
				\end{enumerate}
				
				Los juegos en los que la IA ha tenido más injerencia son los dinámicos, debido a que cada uno de ellos involucra la toma de decisiones y, en principio, un comportamiento inteligente. La gran mayoría de los esfuerzos que se han realizado en esta área pertenecen a lo que se considera IA suave, es decir al cálculo y evaluación de algoritmos, en su mayoría heurísticos, que han probado ser exitosos al llevarlos a la práctica. Pero lamentablemente, se ha investigado poco en la forma cómo los humanos realizan el proceso de enfrentarse a dichos juegos, porque los seres humanos trabajan con conceptos y con reconocimiento de patrones \cite{Restle:uq}.\\
				
				De acuerdo con Restle y Greeno (1970) los seres humanos somos capaces de entender cómo jugar a través de estímulos y patrones \cite{Restle:uq}. Esto implica un problema computacional, dado que en lo que respecta a la IA, el reto consiste en permitir que un computador logre pensar como lo hace un humano y esto se ha malogrado a través del tiempo, precisamente porque se ha investigado poco sobre cómo emular esta característica humana.\\
				
				La tesis que se propone en este documento se centra en el reconocimiento de patrones en la evaluación de juegos, de modo que se asemeje más a la forma como un ser humano lo hace, dejando de lado los análisis por fuerza bruta que son característicos de los programas actuales. El tipo de juego para el cual está desarrollada esta propuesta son los dinámicos con información completa.\\
				
				La razón para haber escogido los juegos de información completa es que al ser los más estudiados y para los cuales ya existen programas basados en análisis por fuerza bruta, esto provee un marco de referencia para establecer una comparación. Por lo tanto es medible si el reconocimiento de patrones realmente es exitoso al contrastarlo contra la evaluación de los programas tradicionales a los cuales se tenga acceso.
				
				\section{El algoritmo minimax}
				De manera tradicional se ha utilizado el mismo enfoque para atacar el problema de los juegos de información completa. Se trata del árbol de minimax, un árbol de juego que permite que se representen todas las posibles jugadas que se pueden hacer con un nivel de profundidad (altura del árbol) que depende de la capacidad de memoria que tiene la computadora en la que se está ejecutando.\\
				
				Consiste en el cálculo simple recurrente de los valores de minimax del estado sucesor, directamente implementando las ecuaciones de la definición. La recursión avanza hacia las hojas del árbol y entonces los valores minimax retroceden por el árbol cuando la recursión se va deshaciendo \cite{Russell_2004}.
				
				Dentro de las ventajas que tiene el algoritmo minimax se resalta que ha sido exitoso. Gracias a este se ha podido desarrollar completamente el árbol de juego de las damas y por lo tanto se ha podido encontrar el juego perfecto, sabiendo que si ambas partes juegan perfectamente, se consiguen las tablas \cite{cbc_checkers:fk}. Las principales desventajas del minimax son el gran tiempo que necesita para calcular las variantes y en el espacio que requiere, por ejemplo el tablero necesitó de más de 5 x \(10^{14}\) posiciones diferentes para completar el árbol \cite{cbc_checkers:fk}. 
				
				
				
				\section{Hipótesis}\label{sec:Hipotesis}
				La hipótesis que se defiende en esta tesis es \textbf{ “El reconocimiento de patrones es efectivo en el análisis del estado de juegos que involucran toma de decisiones con información completa con una varianza aceptable” }
				
				Es muy importante recalcar que se tiene actualmente una necesidad de tener rivales computacionales que hagan variar su nivel y que consuman pocos recursos. Por ejemplo, se necesita que hayan programas de pelea que logren simular diferentes personalidades para diferentes juegos estratégicos \textit{online}. \cite{FangChanNair:uq}
				
				Dado que estos servidores atienden a muchos clientes de manera simultánea, sus recursos no son suficientes para asignar a los procesos adicionales que un programa que juegue requiere. Entonces, por lo general dejan que sean los mismos usuarios que hagan su aporte con sus propios programas; sin embargo, si se lograra crear un proceso que de manera barata pueda jugar y que además lo haga bien, pues sería un importante servicio que se brinde a los usuarios en general.

			\section{Plan general del trabajo}
			Los capítulos siguientes están dispuestos de la manera que se describe a continuación:\\
			
			\begin{enumerate}
				\item[\textbf{Capítulo 2:}] Expone la necesidad de trabajar con representaciones no simbólicas en el ámbito de la inteligencia 
				artificial y los esfuerzos que se han hecho en esta área.\\
				
				\item[\textbf{Capítulo 3:}] Presenta algunos factores humanos, históricos y técnicos de cómo ha sido abordado el ajedrez como 
				un reto intelectual. También expone las características que se toman en cuenta en una partida de ajedrez a la hora de valorarla 
				por parte de un experto humano.\\
				
				%\item[\textbf{Capítulo 4:}]\\
				
				\item[\textbf{Capítulo 4:}] Explica los métodos que se van a utilizar para presentar las posiciones a la red neuronal.\\
				
				\item[\textbf{Capítulo 5:}] Este capítulo muestra las posiciones que van a tomarse en cuenta en la selección de la base de 
				entrenamiento, tomando los puntos más importantes señalados en los capítulos anteriores.\\
				
				\item[\textbf{Capítulo 6:}] Este capítulo se encuentra dividido en dos fases: la primera consiste en el diseño 
				de los factores que se van a tomar en cuenta para la valoración de la red y la comparación de ésta con las valoraciones humanas. 
				La segunda consiste en la exposición y valoración estadística de los resultados.\\
				
				\item[\textbf{Capítulo 7:}] Este capítulo expone las conclusiones a las que se llegó a lo largo de esta tesis, basadas en el 
				experimento del capítulo 6. Este capítulo finaliza con trabajo futuro que puede darse a partir de esta tesis en el área de estudio\\
			\end{enumerate}